'''
84. 柱状图中最大的矩形
难度
困难

733

收藏

分享

切换为英文

关注

反馈
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。


以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。


图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

'''



class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        size=len(heights)+2
        heights=[0]+heights+[0]
        stack=[0]
        res=0

        for i in range(1,size):
            while heights[i]<heights[stack[-1]]:
                cur_height=heights[stack.pop()]#遇到比当前小的，根据入栈条件，可知当前柱高度大于左右两边的柱（右边柱紧邻，左边柱由栈顶位置确定），出栈
                cur_width=i-stack[-1]-1#计算当前柱与栈顶（左边最近的柱）的距离
                res=max(res,cur_height*cur_width)
            stack.append(i)
        return res
'''
题解过程：
    1.从左向右考虑，如果对于当前的柱，它的高度大于左右边离它最近的柱的高度，则以这个高度的最大矩形可以确定。找到这个矩形后，可以将该柱去掉，在后面的计算中不再需要这个柱，根据这个特点，可以使用栈。
    2.在上面这个过程中，如果当前柱的高度，大于栈顶柱的高度，则直接入栈；如果当前柱的高度，小于栈顶的高度，则先进行出栈，寻找栈顶高度的最大矩形，再将当前柱入栈。
        这样顺带处理了“它的高度大于左右边离它最近的柱的高度”这一条件。
    3.加入哨兵，两端填上0，这样就不用检查栈是否空



'''